Decision Tree Regression

Decision Tree를 이용한 Regression.

Decision Tree에서 데이터를 split하는 기준이 Information Gain이었다면, Regerssion에서는 MSE for node를 이용한다.

\frac{1}{N _{m}} t \sum b_{m} (x^{t}) (r^{t} - g_{m})^{2}

$b_{m} (x) = {10 if x reaches node m otherwise$
$g_{m} = \frac{t \sum b _{m} ( x ^{t} ) r ^{t}}{t \sum b _{m} ( x ^{t} )}$ : 평균 label 값.

이 때, MSE가 일종의 Variance로 볼 수 있는데 Split된 값들 끼리 label이 비슷하기를 원하므로 Variance가 작은 것을 선호한다.

split 후의 Average MSE는

\frac{1}{N _{m}} j \sum t \sum b_{m \to j} (x^{t}) (r^{t} - g_{m \to j})^{2}

$b_{m \to j} (x) = {10 if x reaches node m and takes branch j otherwise$
$g_{m \to j} = \frac{t \sum b _{m \to j} ( x ^{t} ) r ^{t}}{t \sum b _{m \to j} ( x ^{t} )}$

즉, Split을 한 후의 Variance 차이가 큰 것을 이용한다.

\frac{1}{N _{m}} t \sum b_{m} (x^{t}) (r^{t} - g_{m})^{2} - \frac{1}{N _{m}} j \sum t \sum b_{m \to j} (x^{t}) (r^{t} - g_{m \to j})^{2}

Tree Learning Algorithm for Regression

Decrease in MSE, Tree Learning Algorithm에서 Decision Tree와 동일하게 하되, Information Gain이 큰 것 대신 Decrease in MSE가 큰 것을 고른다.
또한, 반환값 역시 class 대신 평균 label 값인 $g_{m}$ 을 반환한다.
- 혹은, $g (x) = w_{m}^{⊤} x + w_{m 0}$ : 방식의 Linear Regression fit 방식을 이용할 수도 있다. $m$ Node에 속한 $x$ 를 가지고 Regression한다.
MSE( $D_{j}$ )가 Threshold보다 작으면 Leaf Node로 만든다.
- Threshold가 작아질수록 Tree가 커지니 적절한 Threshold를 찾아야 한다.

평균 label 값 $g (x) = w^{⊤} x + w_{m 0}$ 으로, Linear Regression을 이용해 $m$ 노드에 속한 $x$ 를 가지고 regression을 해 값을 추정할 수도 있다.